package com.sorted;

import java.util.Arrays;

/**
 * 选定一个基准值pivot（通常指定为数组第一个值），比基准值大的放在右侧，比基准值小的放在左侧
 * 指定左右两个指针分别为left，right ；left < right
 * 指定函数退出条件，即left > right
 * 先从右向左遍历，即右指针向左移动——right–操作，发现比pivot小的值暂停移动
 * 再从左向右遍历，即左指针向右移动——left++操作，发现比pivot大的值暂停移动
 * 交换左右指针发现的两个值的位置
 * 当两指针相遇，即left == right，当前值与pivot交换位置
 *
 */
public class QuickSort {

    public static void main(String[] args) {

        int [] arr = {1,3,5,7,9,8,6,4,2,-1};

        qsort(arr,0,arr.length-1);

        System.out.println(Arrays.toString(arr));



    }

    public static void qsort(int [] array,int low,int high){
        if (low>=high)
        {
            return ;
        }

        int pivot = array[low];
        int left = low;
        int right = high;
        int t = 0;
        //遍历条件 左右指针
        while (left < right){

            //右侧遍历
            while (left < right && array[right]>=pivot){
                right--;
            }
            //左侧遍历
            while (left < right && array[left]<=pivot){
                left++;
            }


            if (left<right){
                t = array[left];
                array[left] = array[right];
                array[right] = t;
            }

        }

        //相遇
        array[low] = array[left];
        array[left] = pivot;

        //左侧递归
        if (low <left){
            qsort(array,low,left-1);
        }
        //右侧递归
        if(right <high){
            qsort(array,right+1,high);
        }


    }
}
